package binary_tree

import "math"

//144. 二叉树的前序遍历
//https://leetcode-cn.com/problems/binary-tree-preorder-traversal
var preRes []int

//前序遍历-递归
func PreorderTraversal(root *TreeNode) []int {
	preRes = make([]int, 0)
	preHelper(root)
	return preRes
}

func preHelper(root *TreeNode) {
	if root == nil {
		return
	}

	preRes = append(preRes, root.Val)
	preHelper(root.Left)
	preHelper(root.Right)
}

//前序遍历-迭代
//前序的特点是：根-左-右
//可以利用栈的特点: 第一次先将根入栈
//循环体判断栈不为空，则取出一个;判断右节点不为空则入栈，再入左栈。
//这样最终是右节点最后出来的，满足前序遍历
func PreorderTraversalIt(root *TreeNode) []int {
	stack := make([]*TreeNode, 0) //使用slice模拟栈
	output := make([]int, 0)      //输出
	if root != nil {
		stack = append(stack, root)
	}

	for len(stack) != 0 {
		//先取出栈的内容
		node := stack[len(stack)-1]
		//重新切片，去掉最后一个值。注意切片切割操作是不含最后一个index的
		stack = stack[0 : len(stack)-1]
		output = append(output, node.Val)

		//先右边节点入栈。注意栈是后进先出的
		if node.Right != nil {
			stack = append(stack, node.Right)
		}

		//再入左侧节点。这样下一次遍历左侧节点输出
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return output
}

//94. 二叉树的中序遍历
//https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
var inRes []int

//中序遍历-递归
func InorderTraversal(root *TreeNode) []int {
	inRes = make([]int, 0)
	inHelper(root)
	return inRes
}

func inHelper(root *TreeNode) {
	if root == nil {
		return
	}

	inHelper(root.Left)
	inRes = append(inRes, root.Val)
	inHelper(root.Right)
}

//中序遍历-迭代
//特点：左-根-右
func InorderTraversalIt(root *TreeNode) []int {
	stack := make([]*TreeNode, 0)
	output := make([]int, 0)
	curr := root

	for curr != nil || len(stack) != 0 {
		//将所有左侧节点入到栈
		for curr != nil {
			stack = append(stack, curr)
			curr = curr.Left
		}

		//取出节点
		curr = stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		output = append(output, curr.Val)

		//curr指向右侧
		curr = curr.Right
	}

	return output
}

//145. 二叉树的后序遍历
//https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
var postRes []int

//后序遍历-递归
func PostorderTraversal(root *TreeNode) []int {
	postRes = make([]int, 0)
	postHelper(root)
	return postRes
}

func postHelper(root *TreeNode) {
	if root == nil {
		return
	}

	postHelper(root.Left)
	postHelper(root.Right)
	postRes = append(postRes, root.Val)
}

//后序遍历-迭代
//示例:
//    1
//   / \
//  2   3
// / \
//4  5
//前序:(根-左-右) 1-2-4-5-3
//中序:(左-根-右) 4-2-5-1-3
//后序:(左-右-根) 4-5-2-3-1
//(根-右-左): 1-3-2-5-4 再反序得到后序遍历的结果: 4-5-2-3-1
//所以后序的迭代可以使用上面的小技巧，对前序遍历迭代改一下入栈顺序，再对输出逆序即可
func PostorderTraversalIt(root *TreeNode) []int {
	stack := make([]*TreeNode, 0) //使用slice模拟栈
	output := make([]int, 0)      //输出
	if root != nil {
		stack = append(stack, root)
	}

	for len(stack) != 0 {
		//先取出栈的内容
		node := stack[len(stack)-1]
		//重新切片，去掉最后一个值。注意切片切割操作是不含最后一个index的
		stack = stack[0 : len(stack)-1]
		output = append([]int{node.Val}, output...) //每次在输出的前面加元素，使得结果逆序
		//output = append(output, node.Val)

		//再入左侧节点。这样下一次遍历右侧节点输出
		if node.Left != nil {
			stack = append(stack, node.Left)
		}

		//右边节点入栈。注意栈是后进先出的
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	return output
}

//101. 对称二叉树
//给定一个二叉树，检查它是否是镜像对称的。
//例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
//
//    1
//   / \
//  2   2
// / \ / \
//3  4 4  3
func isSymmetric(root *TreeNode) bool {
	//为空肯定是镜像的
	if root == nil {
		return true
	}

	return isMirror(root.Left, root.Right)
}

func isMirror(left *TreeNode, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	}

	//一个不为空说明不是镜像的
	if left == nil || right == nil {
		return false
	}

	if left.Val == right.Val && isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left) {
		return true
	}

	return false
}

//104. 二叉树的最大深度-递归法
//https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
//时间复杂度：我们每个结点只访问一次，因此时间复杂度为 O(N)O(N)
func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return int(math.Max(float64(MaxDepth(root.Left)), float64(MaxDepth(root.Right))) + 1)
}

// 二叉树的最大深度-迭代法
//可以在栈的帮助下将上面的递归转换为迭代。
func MaxDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var queue []*TreeNode       // 辅助队列
	queue = append(queue, root) // 根节点入队
	depth := 0                  // 初始化深度为0

	for len(queue) > 0 { // 当队列不为空时，循环以下操作
		size := len(queue)          //当前队列中元素个数size作为限定:当前层级中节点数量
		for i := 0; i < size; i++ { // 遍历当前层级中的节点
			s := queue[0]      // 获取队首元素
			queue = queue[1:]  // 队首元素出队
			if s.Left != nil { // 如果左子树不为空，左子树入队
				queue = append(queue, s.Left)
			}
			if s.Right != nil { // 如果右子树不为空，右子树入队
				queue = append(queue, s.Right)
			}
		}
		depth++ // for循环结束后这一层级节点已经访问结束，深度加+1
	}
	return depth
}
